package 力扣_树算法.搜索树;


/**669. 修剪二叉搜索树
 * @author zx
 * @create 2022-04-17 15:13
 */
public class Num669 {
    /**
     好理解版本的精简!
     */
    public TreeNode trimBST3(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {
            //因为是二叉搜索树,节点.left < 节点 < 节点.right
            //节点数字比low小,就把左节点全部裁掉.裁掉之后,继续看右节点的剪裁情况.
            return trimBST(root.right, low, high);
        } else if (root.val > high) {
            //如果数字比high大,就把右节点全部裁掉.
            //裁掉之后,继续看左节点的剪裁情况
            return trimBST(root.left, low, high);
        }  else {
            // root在[low,high]范围内
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);
        }
        return root;
    }
    /**
     * @return 好理解的版本
     */
    public TreeNode trimBST2(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {
            //因为是二叉搜索树,节点.left < 节点 < 节点.right
            //节点数字比low小,就把左节点全部裁掉.
            root = root.right;
            //裁掉之后,继续看右节点的剪裁情况.剪裁后重新赋值给root
            root = trimBST(root, low, high);
        } else if (root.val > high) {
            //如果数字比high大,就把右节点全部裁掉.
            root = root.left;
            //裁掉之后,继续看左节点的剪裁情况
            root = trimBST(root, low, high);
        } else {
            //如果数字在区间内,就去裁剪左右子节点.
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);
        }
        return root;
    }

    /**
     * @return 官方题解(看着简单,思维量巨大)
     */
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) {
            return root;
        }
        if (root.val > R) {
            //当前节点和右子树的所有值都不可能在[low,high]内,但是左子树的值都小于根节点
            //有可能存在节点位于[low,high]内,递归判断左子树的节点trimBST(root.left,low,high)

            return trimBST(root.left, L, R);
        }
        if (root.val < L) {
            //当前节点和左子树的所有值都不可能在[low, high]内,但是右子树的值都大于根节点
            //有可能存在节点位于[low,high]内,递归判断右子树的节点trimBST(root.right,low,high)
            return trimBST(root.right, L, R);
        }
        //如果当前节点处于给定的边界内，那么就递归的判断节点的左右子树
        //假设左右子树中进行了修剪的操作，就会返回上面两种情况中符合边界返回的节点，
        //从而使根节点和修剪后的节点建立了联系
        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);
        return root;
    }
}
